home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 169_01 / sq.c86 < prev    next >
Text File  |  1984-07-27  |  22KB  |  778 lines
  1. /*% cc -O -n % -o sq
  2. */
  3. #include <stdio.h>
  4. #define TRUE 1
  5. #define rewind(c) fseek(c,0L,0);                       /* 1.7 */
  6. #define FALSE 0
  7. #define ERROR (-1)
  8. #define PATHLEN 312    /* Number of characters allowed in pathname */
  9. #define ALTNAME "sq.out"
  10.  
  11. /* Definitions and external declarations */
  12. #define RECOGNIZE 0xFF76    /* unlikely pattern */
  13. /* *** Stuff for first translation module *** */
  14. #define DLE 0x90
  15.  
  16.  
  17. /* *** Stuff for second translation module *** */
  18. #define SPEOF 256    /* special endfile token */
  19. #define NUMVALS 257    /* 256 data values plus SPEOF*/
  20. /* Definitions and external declarations */
  21. int Usestd;    /* Use stdout for squeezed output */
  22. unsigned crc;    /* error check code */
  23. /* *** Stuff for first translation module *** */
  24. int likect;    /*count of consecutive identical chars */
  25. int lastchar, newchar;
  26. char state;
  27. /* states */
  28. #define NOHIST    0    /*don't consider previous input*/
  29. #define SENTCHAR 1    /*lastchar set, no lookahead yet */
  30. #define SENDNEWC 2    /*newchar set, previous sequence done */
  31. #define SENDCNT 3    /*newchar set, DLE sent, send count next */
  32.  
  33. /* *** Stuff for second translation module *** */
  34. #define NOCHILD -1    /* indicates end of path through tree */
  35. #define NUMNODES (NUMVALS + NUMVALS - 1)    /* nbr of nodes */
  36.  
  37. #define MAXCOUNT 65535    /* biggest unsigned integer */
  38.  
  39. /* The following array of structures are the nodes of the
  40.  * binary trees. The first NUMVALS nodes becomethe leaves of the
  41.  * final tree and represent the values of the data bytes being
  42.  * encoded and the special endfile, SPEOF.
  43.  * The remaining nodes become the internal nodes of the final tree.
  44.  */
  45.  
  46. struct    nd {
  47.     unsigned weight;    /* number of appearances */
  48.     int tdepth;        /* length on longest path in tre*/
  49.     int lchild, rchild;    /* indexes to next level */
  50. }
  51. node[NUMNODES];
  52.  
  53. int dctreehd;    /*index to head node of final tree */
  54.  
  55. /* This is the encoding table:
  56.  * The bit strings have first bit in  low bit.
  57.  * Note that counts were scaled so code fits unsigned integer
  58.  */
  59.  
  60. int codelen[NUMVALS];        /* number of bits in code */
  61. unsigned code[NUMVALS];     /* code itself, right adjusted */
  62. unsigned tcode;         /* temporary code value */
  63.  
  64.  
  65. /* Variables used by encoding process */
  66. int curin;    /* Value currently being encoded */
  67. int cbitsrem;    /* Number of code string bits remaining */
  68. unsigned ccode; /* Current code shifted so next code bit is at right */
  69. /* This program compresses a file without losing information.
  70.  * The usq.com program is required to unsqueeze the file
  71.  * before it can be used.
  72.  *
  73.  * Typical compression rates are:
  74.  *    .COM    6%    (Don't bother)
  75.  *    .ASM    33%    (using full ASCII set)
  76.  *    .DIC    46%    (using only uppercase and a few others)
  77.  * Squeezing a really big file takes a few minutes.
  78.  *
  79.  * Useage:
  80.  *    sq file ...
  81.  *
  82.  *
  83.  * The squeezed file name is formed by changing the second from last
  84.  * letter of the file type to Q. If there is no file type,
  85.  * the squeezed file type is QQQ. If the name exists it is
  86.  * overwritten!
  87.  *
  88.  * The transformations compress strings of identical bytes and
  89.  * then encode each resulting byte value and EOF as bit strings
  90.  * having lengths in inverse proportion to their frequency of
  91.  * occurrance in the intermediate input stream. The latter uses
  92.  * the Huffman algorithm. Decoding information is included in
  93.  * the squeezed file, so squeezing short files or files with
  94.  * uniformly distributed byte values will actually increase size.
  95.  */
  96.  
  97. /* CHANGE HISTORY:
  98.  * 1.5u **nix version - means output to stdout.
  99.  *  (stdin not allowed becuase sq needs to rewind input, which
  100.  *  won't work with pipes.)
  101.  * Filename generation changed to suit **nix and stdio.
  102.  * 1.6u machine independent output for file compatibility with
  103.  *    original CP/M version SQ, when running on machine with
  104.  *    IBM byte ordering such as Z8000 and 68000.
  105.  *
  106.  * 1.7    08/13/83  C86 Version by Wayne Fruhwald
  107.  *    Converted to work with Computer Innovation's C86 c compiler under MSDOS.
  108.  *
  109.  */
  110.  
  111. #define VERSION "1.7    8-13-83"                                       /* 1.7 */
  112.  
  113. main(argc, argv)
  114. int argc;
  115. char *argv[];
  116. {
  117.     register i,c;
  118.  
  119.  
  120.     /* Process the parameters in order */
  121.     for(i = 1; i < argc; ++i) {
  122.         if(strcmp(argv[i], "-")==0)
  123.             Usestd = TRUE;
  124.     }
  125.     for(i = 1; i < argc; ++i) {
  126.         if(strcmp(argv[i], "-")!=0)
  127.             obey(argv[i]);
  128.     }
  129.  
  130.     if(argc < 2) {
  131.         fprintf(stderr,"File squeezer version %s by\n\tRichard Greenlaw\n\t251 Colony Ct.\n\tGahanna, Ohio 43230\n", VERSION);
  132.         fprintf(stderr, "Usage: sq [-] pathname ...\n");
  133.         fprintf(stderr, "\t- squeezed output to stdout\n");
  134.         exit(1);
  135.     }
  136.     exit(0);
  137. }
  138.  
  139. obey(p)
  140. char *p;
  141. {
  142.     char *w,*q;
  143.     char outfile[PATHLEN+2];    /* output file spec. */
  144.  
  145.     /* First build output file name */
  146.  
  147.     strcpy(outfile, p);
  148.     /* Find and change output file type */
  149.     for(w=q = outfile; *q != '\0'; ++q)     /* skip leading /'s */
  150.         if( *q == '/')
  151.             w = q+1;
  152.     for(q = w; *q != '\0'; ++q)
  153.         if(*q == '.')
  154.             if(*(q + 1) == '\0')
  155.                 *q = '\0';      /* kill trailing dot */
  156.             else
  157.                 switch(*(q+2)) {
  158.                 case 'q':
  159.                 case 'Q':
  160.                     fprintf(stderr, "\n%s ignored ( already squeezed?)", p);
  161.                     return;
  162.                 case '\0':
  163.                     *(q+3) = '\0';
  164.                     /* fall thru */
  165.                 default:
  166.                     *(q + 2) = 'Q';
  167.                     goto named;
  168.                 }
  169.     /* No file type */
  170.     strcat(outfile, ".QQQ");
  171. named:
  172.     if(strlen(w)>14)
  173.         strcpy(outfile, ALTNAME);    /* check for too long name */
  174.     squeeze(p, outfile);
  175. }
  176.  
  177. squeeze(infile, outfile)
  178. char *infile, *outfile;
  179. {
  180.     register i, c;
  181.     FILE *inbuff, *outbuff; /* file buffers */
  182.  
  183.     fprintf(stderr, "\n%s -> %s: ", infile, outfile);
  184.  
  185.     if((inbuff=fopen(infile, "rb")) == NULL) {                     /* 1.7 */
  186.         fprintf(stderr, "Can't open %s for input pass 1\n", infile);
  187.         return;
  188.     }
  189.     if(Usestd)
  190.         outbuff=stdout;
  191.     else if((outbuff=fopen(outfile, "wb")) == NULL) {              /* 1.7 */
  192.         fprintf(stderr, "Can't create %s\n", outfile);
  193.         fclose(inbuff);
  194.         return;
  195.     }
  196.  
  197.     /* First pass - get properties of file */
  198.     crc = 0;    /* initialize checksum */
  199.     fprintf(stderr, "analyzing, ");
  200.     init_ncr();
  201.     init_huff(inbuff);
  202.     rewind(inbuff);
  203.     /* Write output file header with decoding info */
  204.     wrt_head(outbuff, infile);
  205.  
  206.     /* Second pass - encode the file */
  207.     fprintf(stderr, "squeezing, ");
  208.  
  209.     init_ncr();    /* For second pass */
  210.  
  211.     /* Translate the input file into the output file */
  212.     while((c = gethuff(inbuff)) != EOF)
  213.         if(putc(c, outbuff) == ERROR && ferror(outbuff)) {
  214.             fprintf(stderr, "ERROR - write failure in %s\n", outfile);
  215.             goto closeall;
  216.         }
  217.     fprintf(stderr, " done.\n");
  218. closeall:
  219.     fclose(inbuff);
  220. closeout:
  221.     fflush(outbuff);
  222.     fclose(outbuff);
  223. }
  224.  
  225.  
  226. /* First translation - encoding of repeated characters
  227.  * The code is byte for byte pass through except that
  228.  * DLE is encoded as DLE, zero and repeated byte values
  229.  * are encoded as value, DLE, count for count >= 3.
  230.  */
  231.  
  232. init_ncr()    /*initialize getcnr() */
  233. {
  234.     state = NOHIST;
  235. }
  236.  
  237. int
  238. getcnr(iob)
  239. FILE *iob;
  240. {
  241.     switch(state) {
  242.     case NOHIST:
  243.         /* No relevant history */
  244.         state = SENTCHAR;
  245.         return lastchar = getc_crc(iob);
  246.     case SENTCHAR:
  247.         /* Lastchar is set, need lookahead */
  248.         switch(lastchar) {
  249.         case DLE:
  250.             state = NOHIST;
  251.             return 0;    /* indicates DLE was the data */
  252.         case EOF:
  253.             return EOF;
  254.         default:
  255.             for(likect = 1; (newchar = getc_crc(iob)) == lastchar && likect < 255; ++likect)
  256.                 ;
  257.             switch(likect) {
  258.             case 1:
  259.                 return lastchar = newchar;
  260.             case 2:
  261.                 /* just pass through */
  262.                 state = SENDNEWC;
  263.                 return lastchar;
  264.             default:
  265.                 state = SENDCNT;
  266.                 return DLE;
  267.             }
  268.         }
  269.     case SENDNEWC:
  270.         /* Previous sequence complete, newchar set */
  271.         state = SENTCHAR;
  272.         return lastchar = newchar;
  273.     case SENDCNT:
  274.         /* Sent DLE for repeat sequence, send count */
  275.         state = SENDNEWC;
  276.         return likect;
  277.     default:
  278.         fprintf(stderr,"Bug - bad state\n");
  279.         exit(1);
  280.         /* NOTREACHED */
  281.     }
  282. }
  283.  
  284.  
  285. /******** Second translation - bytes to variable length bit strings *********/
  286.  
  287.  
  288. /* This translation uses the Huffman algorithm to develop a
  289.  * binary tree representing the decoding information for
  290.  * a variable length bit string c